package com.zj.leetcode.medium.greed;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @program: algorithm
 * @description: 132 模式
 * 456 132-pattern
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class One32Pattern {
    public static void main(String[] args) {
//        int[] nums = {3,1,4,2};
        int[] nums ={3,5,0,3,4};
        Solution solution = new One32Pattern().new Solution();
        System.out.println(solution.find132pattern(nums));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean find132pattern(int[] nums) {
            int n = nums.length;
            Deque<Integer> candidateK = new LinkedList<Integer>();
            candidateK.push(nums[n - 1]);
            int maxK = Integer.MIN_VALUE;

            for (int i = n - 2; i >= 0; --i) {
                if (nums[i] < maxK) {
                    return true;
                }
                while (!candidateK.isEmpty() && nums[i] > candidateK.peek()) {
                    maxK = candidateK.pop();
                }
                if (nums[i] > maxK) {
                    candidateK.push(nums[i]);
                }
            }

            return false;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
